package IntervalSet.Medium;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

public class LC0452 {
    /**
     * 基于贪心的算法，时间复杂度NlogN
     */
    public int findMinArrowShotsGreedy(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt((int[] array) -> array[1])); // 右边界小的的排前面
        LinkedList<int[]> pointsAsList = new LinkedList<>(Arrays.asList(points));
        // 贪心：每次在右边界最小的气球的右边界处射击
        int nShots = 0;
        while (!pointsAsList.isEmpty()) {
            nShots++;
            int rightBound = pointsAsList.get(0)[1];
            for (int i = 0; i < pointsAsList.size(); ) {
                int[] balloon = pointsAsList.get(i);
                // LinkedList相比ArrayList更加适合随机删除操作
                if (balloon[0] <= rightBound && balloon[1] >= rightBound) pointsAsList.remove(i);
                else if (balloon[0] > rightBound) break;
                else i++;
            }
        }

        return nShots;
    }

    /**
     * 利用交集的方法。将所有区间按照左端点排序；记录第一个区间α，对于之后的每个区间i，如果它与α有交集，则表明i可以一并爆破，
     * 并将记录的区间更新为α∩i；如果i与α没有交集，则需要增加一支箭。
     * 这个解法的时间复杂度和基于贪心的解法是一样的，都是NlogN，但是这种解法可能更直观一点。
     */
    public int findMinArrowShotsIntersection(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt((int[] array) -> array[0])); // 左边界小的的排前面
        int[] intersection = new int[2];
        intersection[0] = points[0][0];
        intersection[1] = points[0][1];
        int nShots = 1;
        for (int i = 1; i < points.length; i++) {
            int[] balloon = points[i];
            if (balloon[0] <= intersection[1]) {
                intersection[0] = balloon[0]; // intersection[0]其实不必记录，为了好看记录一下
                intersection[1] = Math.min(balloon[1], intersection[1]);
            } else {
                nShots++;
                intersection[0] = balloon[0];
                intersection[1] = balloon[1];
            }
        }

        return nShots;
    }
}
